package pers.qianyu.month_202102.date_20210214;

import org.junit.*;

import java.util.*;

/**
 * 765. 情侣牵手
 * https://leetcode-cn.com/problems/couples-holding-hands/
 * - 深搜版本
 *
 * @author mizzle rain
 * @date 2021-02-14 10:48
 */
public class MinSwapsCouples2 {
    private int res = 0;

    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int cnt = n >> 1;
        ArrayList<Integer>[] graph = new ArrayList[cnt];
        for (int i = 0; i < graph.length; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < n; i += 2) {
            int x = row[i] >> 1, y = row[i + 1] >> 1;
            if (x == y) continue;
            graph[x].add(y);
            graph[y].add(x);
        }

        boolean[] visited = new boolean[cnt];
        for (int i = 0; i < graph.length; i++) {
            if (!visited[i]) {
                dfs(graph, visited, i, 0);
            }
        }
        return res;
    }

    private void dfs(ArrayList<Integer>[] graph, boolean[] visited, int cur, int cnt) {
        visited[cur] = true;
        cnt++;
        boolean flag = false;
        for (int x : graph[cur]) {
            if (!visited[x]) {
                flag = true;
                dfs(graph, visited, x, cnt);
            }
        }
        if (!flag) res += cnt - 1;
        //visited[cur] = false;
    }

    @Test
    public void test1() {
        int result = new MinSwapsCouples2()
                .minSwapsCouples(new int[]{0, 2, 1, 3});
        Assert.assertEquals(1, result);
    }
}
